
#include <dim-sum/types.h>
#include <dim-sum/uaccess.h>
#include <dim-sum/sched.h>
#include <dim-sum/kernel.h>
#include <dim-sum/major.h>
#include <dim-sum/string.h>
#include <dim-sum/file.h>
#include <dim-sum/random.h>
#include <dim-sum/syscall.h>
#include <dim-sum/mem.h>
#include <dim-sum/irq.h>

#define RANDPOOL 512

struct random_bucket {
	int add_ptr;
	int entropy_count;
	int length;
	int bit_length;
	int delay_mix:1;
	__u8 *pool;
};

struct timer_rand_state {
	unsigned long	last_time;
	int 		last_delta;
	int 		nbits;
};

static struct random_bucket random_state;
static __u32 rand_pool_key[16];
static __u8 random_pool[RANDPOOL];
static __u32 random_counter[16];
static struct timer_rand_state keyboard_timer_state;
static struct timer_rand_state irq_timer_state[NR_IRQS];

#ifndef MIN
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#endif

#define F1(x, y, z) (z ^ (x & (y ^ z)))
#define F2(x, y, z) F1(z, x, y)
#define F3(x, y, z) (x ^ y ^ z)
#define F4(x, y, z) (y ^ (x | ~z))

#define MD5STEP(f, w, x, y, z, data, s) \
	(w += f(x, y, z) + data,  w = w<<s | w>>(32-s),  w += x)

static void flush_random(struct random_bucket *random_state)
{
	random_state->add_ptr = 0;
	random_state->bit_length = random_state->length * 8;
	random_state->entropy_count = 0;
	random_state->delay_mix = 0;
}

void rand_initialize(void)
{
	random_state.length = RANDPOOL;
	random_state.pool = random_pool;
	flush_random(&random_state);
}

/**
 * MD5算法的核心，它改变了现有的MD5散列，
* 以反映增加了16个长字的新数据。
 * MD5Update阻断数据并将字节转换为长字，用于该程序。
 */
static void md5_trans_form(__u32 buf[4],
			 __u32 const in[16])
{
	__u32 a, b, c, d;

	a = buf[0];
	b = buf[1];
	c = buf[2];
	d = buf[3];

	MD5STEP(F1, a, b, c, d, in[0]+0xd76aa478,  7);
	MD5STEP(F1, d, a, b, c, in[1]+0xe8c7b756, 12);
	MD5STEP(F1, c, d, a, b, in[2]+0x242070db, 17);
	MD5STEP(F1, b, c, d, a, in[3]+0xc1bdceee, 22);
	MD5STEP(F1, a, b, c, d, in[4]+0xf57c0faf,  7);
	MD5STEP(F1, d, a, b, c, in[5]+0x4787c62a, 12);
	MD5STEP(F1, c, d, a, b, in[6]+0xa8304613, 17);
	MD5STEP(F1, b, c, d, a, in[7]+0xfd469501, 22);
	MD5STEP(F1, a, b, c, d, in[8]+0x698098d8,  7);
	MD5STEP(F1, d, a, b, c, in[9]+0x8b44f7af, 12);
	MD5STEP(F1, c, d, a, b, in[10]+0xffff5bb1, 17);
	MD5STEP(F1, b, c, d, a, in[11]+0x895cd7be, 22);
	MD5STEP(F1, a, b, c, d, in[12]+0x6b901122,  7);
	MD5STEP(F1, d, a, b, c, in[13]+0xfd987193, 12);
	MD5STEP(F1, c, d, a, b, in[14]+0xa679438e, 17);
	MD5STEP(F1, b, c, d, a, in[15]+0x49b40821, 22);

	MD5STEP(F2, a, b, c, d, in[1]+0xf61e2562,  5);
	MD5STEP(F2, d, a, b, c, in[6]+0xc040b340,  9);
	MD5STEP(F2, c, d, a, b, in[11]+0x265e5a51, 14);
	MD5STEP(F2, b, c, d, a, in[0]+0xe9b6c7aa, 20);
	MD5STEP(F2, a, b, c, d, in[5]+0xd62f105d,  5);
	MD5STEP(F2, d, a, b, c, in[10]+0x02441453,  9);
	MD5STEP(F2, c, d, a, b, in[15]+0xd8a1e681, 14);
	MD5STEP(F2, b, c, d, a, in[4]+0xe7d3fbc8, 20);
	MD5STEP(F2, a, b, c, d, in[9]+0x21e1cde6,  5);
	MD5STEP(F2, d, a, b, c, in[14]+0xc33707d6,  9);
	MD5STEP(F2, c, d, a, b, in[3]+0xf4d50d87, 14);
	MD5STEP(F2, b, c, d, a, in[8]+0x455a14ed, 20);
	MD5STEP(F2, a, b, c, d, in[13]+0xa9e3e905,  5);
	MD5STEP(F2, d, a, b, c, in[2]+0xfcefa3f8,  9);
	MD5STEP(F2, c, d, a, b, in[7]+0x676f02d9, 14);
	MD5STEP(F2, b, c, d, a, in[12]+0x8d2a4c8a, 20);

	MD5STEP(F3, a, b, c, d, in[5]+0xfffa3942,  4);
	MD5STEP(F3, d, a, b, c, in[8]+0x8771f681, 11);
	MD5STEP(F3, c, d, a, b, in[11]+0x6d9d6122, 16);
	MD5STEP(F3, b, c, d, a, in[14]+0xfde5380c, 23);
	MD5STEP(F3, a, b, c, d, in[1]+0xa4beea44,  4);
	MD5STEP(F3, d, a, b, c, in[4]+0x4bdecfa9, 11);
	MD5STEP(F3, c, d, a, b, in[7]+0xf6bb4b60, 16);
	MD5STEP(F3, b, c, d, a, in[10]+0xbebfbc70, 23);
	MD5STEP(F3, a, b, c, d, in[13]+0x289b7ec6,  4);
	MD5STEP(F3, d, a, b, c, in[0]+0xeaa127fa, 11);
	MD5STEP(F3, c, d, a, b, in[3]+0xd4ef3085, 16);
	MD5STEP(F3, b, c, d, a, in[6]+0x04881d05, 23);
	MD5STEP(F3, a, b, c, d, in[9]+0xd9d4d039,  4);
	MD5STEP(F3, d, a, b, c, in[12]+0xe6db99e5, 11);
	MD5STEP(F3, c, d, a, b, in[15]+0x1fa27cf8, 16);
	MD5STEP(F3, b, c, d, a, in[2]+0xc4ac5665, 23);

	MD5STEP(F4, a, b, c, d, in[0]+0xf4292244,  6);
	MD5STEP(F4, d, a, b, c, in[7]+0x432aff97, 10);
	MD5STEP(F4, c, d, a, b, in[14]+0xab9423a7, 15);
	MD5STEP(F4, b, c, d, a, in[5]+0xfc93a039, 21);
	MD5STEP(F4, a, b, c, d, in[12]+0x655b59c3,  6);
	MD5STEP(F4, d, a, b, c, in[3]+0x8f0ccc92, 10);
	MD5STEP(F4, c, d, a, b, in[10]+0xffeff47d, 15);
	MD5STEP(F4, b, c, d, a, in[1]+0x85845dd1, 21);
	MD5STEP(F4, a, b, c, d, in[8]+0x6fa87e4f,  6);
	MD5STEP(F4, d, a, b, c, in[15]+0xfe2ce6e0, 10);
	MD5STEP(F4, c, d, a, b, in[6]+0xa3014314, 15);
	MD5STEP(F4, b, c, d, a, in[13]+0x4e0811a1, 21);
	MD5STEP(F4, a, b, c, d, in[4]+0xf7537e82,  6);
	MD5STEP(F4, d, a, b, c, in[11]+0xbd3af235, 10);
	MD5STEP(F4, c, d, a, b, in[2]+0x2ad7d2bb, 15);
	MD5STEP(F4, b, c, d, a, in[9]+0xeb86d391, 21);

	buf[0] += a;
	buf[1] += b;
	buf[2] += c;
	buf[3] += d;
}

#undef F1
#undef F2
#undef F3
#undef F4
#undef MD5STEP

/**
 * 这个函数的签名应该是接受random_bucket *作为输入参数
 * 但这让tqueue不高兴。
 */
static void mix_bucket(void *v)
{
	struct random_bucket *r = (struct random_bucket *) v;
	int	i, num_passes;
	__u32 *p;
	__u32 iv[4];

	r->delay_mix = 0;

	memcpy(iv, r->pool + r->length - sizeof(iv), sizeof(iv));

	num_passes = r->length / 16;
	for (i = 0, p = (__u32 *) r->pool; i < num_passes; i++) {
		md5_trans_form(iv, rand_pool_key);
		iv[0] = (*p++ ^= iv[0]);
		iv[1] = (*p++ ^= iv[1]);
		iv[2] = (*p++ ^= iv[2]);
		iv[3] = (*p++ ^= iv[3]);
	}
	memcpy(rand_pool_key, r->pool, sizeof(rand_pool_key));

	/* Wipe iv from memory */
	memset(iv, 0, sizeof(iv));

	r->add_ptr = 0;
}

/**
 * 这个函数将一个字节添加到熵 "池 "中。 它并不更新熵的估计值
 */
static inline void add_entropy_byte(struct random_bucket *r,
				    const __u8 ch, int delay)
{
	if (!delay && r->delay_mix)
		mix_bucket(r);
	r->pool[r->add_ptr++] ^= ch;
	if (r->add_ptr >= r->length) {
		if (delay) {
			r->delay_mix = 1;
			r->add_ptr = 0;
		} else
			mix_bucket(r);
	}
}

/**
 * 这个函数在熵池中增加一些字节，并适当地更新熵的数量
 */
static void add_entropy(struct random_bucket *r, const __u8 *ptr,
		 int length, int entropy_level, int delay)
{
	while (length-- > 0)
		add_entropy_byte(r, *ptr++, delay);

	r->entropy_count += entropy_level;
	if (r->entropy_count > r->length*8)
		r->entropy_count = r->length * 8;
}

/**
 * 这个函数通过使用定时延时将熵添加到熵 "池 "中。
 * 它使用 timer_rand_state 结构来估计这个调用给池子增加了多少比特的熵。
 */
static void add_timer_randomness(struct random_bucket *r,
				 struct timer_rand_state *state, int delay)
{
	int	delta, delta2;
	int	nbits;

	/**
	 * 计算我们可能添加的随机性的位数
     * 我们考虑到一阶和二阶delta，以便做出估计
	 */
	delta = jiffies - state->last_time;
	delta2 = delta - state->last_delta;
	state->last_time = jiffies;
	state->last_delta = delta;
	if (delta < 0)
	delta = -delta;
	if (delta2 < 0)
	delta2 = -delta2;
	delta = MIN(delta, delta2) >> 1;
	for (nbits = 0; delta; nbits++)
		delta >>= 1;

	add_entropy(r, (__u8 *) &jiffies, sizeof(jiffies),
		    nbits, delay);

}

void add_keyboard_randomness(unsigned char scancode)
{
	struct random_bucket *r = &random_state;

	add_timer_randomness(r, &keyboard_timer_state, 0);
	add_entropy_byte(r, scancode, 0);
	r->entropy_count += 6;
	if (r->entropy_count > r->bit_length)
		r->entropy_count = r->bit_length;
}

void add_interrupt_randomness(int irq)
{
	struct random_bucket *r = &random_state;

	if (irq >= NR_IRQS)
		return;

	add_timer_randomness(r, &irq_timer_state[irq], 1);
}

/**
 * 这个函数从 "熵池 "中提取随机性，并在一个缓冲区中返回
 * 这个函数计算出池子里还剩下多少比特的熵，但它并不限制实际获得的字节数
 */
static inline int extract_entropy(struct random_bucket *r, char *buf,
				  int nbytes, int to_user)
{
	int length, ret, passes, i;
	__u32 tmp[4];
	u8 *cp;

	add_entropy(r, (u8 *) &jiffies, sizeof(jiffies), 0, 0);

	if (r->entropy_count > r->bit_length)
		r->entropy_count = r->bit_length;
	if (nbytes > 32768)
		nbytes = 32768;
	ret = nbytes;
	r->entropy_count -= ret * 8;
	if (r->entropy_count < 0)
		r->entropy_count = 0;
	passes = r->length / 64;
	while (nbytes) {
		length = MIN(nbytes, 16);
		for (i = 0; i < 16; i++) {
			if (++random_counter[i] != 0)
				break;
		}
		tmp[0] = 0x67452301;
		tmp[1] = 0xefcdab89;
		tmp[2] = 0x98badcfe;
		tmp[3] = 0x10325476;
		md5_trans_form(tmp, random_counter);
		for (i = 0, cp = r->pool; i < passes; i++, cp += 64)
			md5_trans_form(tmp, (__u32 *) cp);
		if (to_user)
			copy_to_user(buf, tmp, length);
		else
			memcpy(buf, tmp, length);
		nbytes -= length;
		buf += length;
	}
	return ret;
}

/**
 * 这个函数是导出的内核接口
 * 它返回一些好的随机数，适合用于TCP等等
 */
void get_random_bytes(void *buf, int nbytes)
{
	extract_entropy(&random_state, (char *) buf, nbytes, 0);
}

int read_random(struct file *file, char *buf, int nbytes)
{
	if ((nbytes * 8) > random_state.entropy_count)
		nbytes = random_state.entropy_count / 8;

	return extract_entropy(&random_state, buf, nbytes, 1);
}

int read_random_unlimited(struct file *file,
			  char *buf, int nbytes)
{
	return extract_entropy(&random_state, buf, nbytes, 1);
}
